//https://www.nowcoder.com/practice/23462ed010024fcabb7dbd3df57c715e?tpId=46&tqId=29115&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-ranking
/*
 * 最短路径和，二维数组 [[1,2],[4.6],[2,8]]
 *
 * */
public class Solution {
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        for (int i = 1; i < col; i++) {
            grid[0][i] = grid[0][i - 1] + grid[0][i];
        }
        for (int i = 1; i < row; i++) {
            grid[i][0] = grid[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
            }
        }
        return grid[row - 1][col - 1];
    }

    /*
     * 一个数组搞定
     * */
    public int minPathSum2(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int[] array = new int[col];
        array[0] = grid[0][0];
        for (int i = 1; i < col; i++) {
            array[i] = array[i - 1] + grid[0][i];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (j == 0) {
                    array[0] = array[0] + grid[i][0];
                } else {
                    array[j] = min(array[j - 1], array[j]) + grid[i][j];
                }
            }
        }
        return array[col - 1];
    }
}